package com.hy.dp.stock;

public class BuySaleStock {

    /**
     * 121. 买卖股票的最佳时机
     * 力扣题目链接
     *
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     *
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     *
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     * 示例 1：
     * 输入：[7,1,5,3,6,4]
     * 输出：5
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     *
     * 思路
     * 1.暴力
     * 这道题目最直观的想法，就是暴力，找最优间距了。
     *
     * 2.贪心
     * 因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
     *
     * 3.动态规划
     * 动规五部曲分析如下：
     *
     * 1. 确定dp数组（dp table）以及下标的含义
     * dp[i][0] 表示第i天持有股票所得最多现金 ，这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？
     *
     * 其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。
     *
     * dp[i][1] 表示第i天不持有股票所得最多现金
     *
     * 注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态
     *
     * 很多同学把“持有”和“买入”没分区分清楚。
     *
     * 在下面递推公式分析中，我会进一步讲解。
     *
     * 2.确定递推公式
     * 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
     *
     * 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
     * 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
     * 那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
     *
     * 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
     *
     * 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
     * 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
     * 同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
     *
     * 3.dp数组如何初始化
     * 由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出
     *
     * 其基础都是要从dp[0][0]和dp[0][1]推导出来。
     *
     * 那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
     *
     * dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
     *
     * 4.确定遍历顺序
     * 从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。
     *
     * 5.举例推导dp数组
     * 以示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：
     *
     * @param price
     * @return
     */
    // 1.暴力破解 时间复杂度：O(n2)  空间复杂度：O(1)
    public static int buySaleStock(int [] price){
        int res = 0;
        for (int i = 0; i < price.length; i++) {
            for (int j = 1; j < price.length; j++) {
                res = Math.max(res,price[j] - price[i]);
            }
        }
        return res;
    }

    //2.贪心算法
    public static int buySaleStock02(int [] price){
        // res不断更新，直到数组循环完毕
        int res = 0;
        // 找到一个最小的购入点
        int low = Integer.MAX_VALUE;

        for (int i = 0; i < price.length; i++) {
            // 获取最小的值
            low = Math.min(low,price[i]);
            res = Math.max(price[i] - low,res);
        }
        return res;
    }
    // 3.动态规划  版本1
    public static int buySaleStock03(int [] price){
        if (price == null || price.length == 0){
            return 0;
        }
        int len = price.length;
        //1. 定义dp数组以及下标定义
        int [][] dp = new int[len][2];
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int res = 0;

        //2.推导递推式

        //3.初始化
        dp[0][0] = -price[0];
        dp[0][1] = 0;

        //4.循环遍历
        for (int i = 1; i < len; i++) {
            // 持有
            dp[i][0] = Math.max(dp[i-1][0],-price[i]);
            // 卖出
            dp[i][1] = Math.max(dp[i-1][0] + price[i],dp[i-1][1]);
        }
        return dp[len - 1][1];
    }
    // 3-2.动态规划  版本2
    public static int buySaleStock04(int [] price){
        int len = price.length;
        int [] dp = new int[2];
        // 记录一次交易，一次交易有买入卖出两种状态
        // 0代表持有，1代表卖出
        dp[0] = -price[0];
        dp[1] = 0;
        // 可以参考斐波那契问题的优化方式
        // 我们从 i=1 开始遍历数组，一共有 prices.length 天，
        // 所以是 i<=prices.length
        for (int i = 1; i <= price.length; i++) {
            // 前一天持有；或当天买入
            dp[0] = Math.max(dp[0],-price[i-1]);
            // 如果 dp[0] 被更新，那么 dp[1] 肯定会被更新为正数的 dp[1]
            // 而不是 dp[0]+prices[i-1]==0 的0，
            // 所以这里使用会改变的dp[0]也是可以的
            // 当然 dp[1] 初始值为 0 ，被更新成 0 也没影响
            // 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行
            dp[1] = Math.max(dp[1],dp[0] + price[i-1]);
        }
        return dp[1];
    }

    public static void main(String[] args) {
        int [] price = {7,1,5,3,6,4};
        System.out.println("暴力破解 res: "+buySaleStock(price));
        System.out.println("贪心算法 res: "+buySaleStock02(price));

        System.out.println("动态规划 res： "+buySaleStock03(price));
        System.out.println("动态规划 res： "+buySaleStock04(price));
    }
}
